package zuo.algo.c18;

import zuo.algo.data.Node;
import zuo.algo.util.TreeUtils;

/**
 * 00:06-二叉搜索树基本操作
 */
public class BST<T extends Comparable<T>> {

    private Node<T> root;

    public int size() {
        return size(root);
    }

    public int size(Node<T> x) {
        if (x == null) {
            return 0;
        } else {
            return x.n;
        }
    }

    public T get(T value) {
        return get(root, value);
    }

    private T get(Node<T> x, T value) {
        if (x == null) {
            return null;
        }
        int cmp = value.compareTo(x.value);
        if (cmp < 0) {
            return get(x.left, value);
        } else if (cmp > 0) {
            return get(x.right, value);
        } else {
            return x.value;
        }
    }

    private void add(T value) {
        root = add(root, value);
    }

    private Node<T> add(Node<T> x, T value) {
        if (x == null) {
            return new Node<>(value, 1);
        }
        int cmp = value.compareTo(x.value);
        if (cmp < 0 ) {
            x.left = add(x.left, value);
        } else if (cmp > 0) {
            x.right = add(x.right, value);
        }
        x.n = size(x.left) + size(x.right) + 1;
        return x;
    }

    public void delete(T key) {
        delete(root, key);
    }

    private Node<T> delete(Node<T> node, T key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.value);
        if (cmp < 0) {
            node.left = delete(node.left, key);
        } else if (cmp > 0) {
            node.right = delete(node.right, key);
        } else {
            // 如果左右都为空，返回空
            // 如果右节点或者左节点为空，返回不为空的节点作为被删除节点父节点的子节点
            // 就是说使用不为空的那个子节点替换该节点
            if (node.right == null) {
                return node.left;
            }
            if (node.left == null) {
                return node.right;
            }
            // 如果左右都不为空，选取右子树的最小节点替换该节点，就是右子树的左子树的第一个左节点为空的节点
            // 该节点大于被删除的节点，所以该节点大于被删除节点的左子树上所有节点，小于被删除节点右子树上其它节点
            Node<T> x = node;
            node = min(x.right);
            // 重新构建该节点，因为该节点左子树为空，并大于被删除节点左子树上所有节点，所以该节点左子树等于被删除节点的左子树即可
            // 右子树的构建等同于将被删除节点的右子树赋给该节点，然后在该节点的右子树中删除该节点
            node.right = resizeRight(x.right);
            node.left = x.left;
        }
        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    private Node<T> resizeRight(Node<T> node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = resizeRight(node.left);
        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    private Node<T> min(Node<T> node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }


    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        bst.add(40);
        bst.add(20);
        bst.add(30);
        bst.add(10);
        bst.add(60);
        bst.add(50);
        bst.add(70);

        TreeUtils.printTree(bst.root);

        bst.add(25);
        bst.add(27);
        bst.add(22);
        bst.add(23);

        TreeUtils.printTree(bst.root);

        bst.delete(20);
        TreeUtils.printTree(bst.root);
    }

}
